class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        DP1 = [0] * len(nums)
        DP2 = [0] * len(nums)
        DP2[0] = nums[0]
        for i in range(1, len(nums)):
            if i == 1:
                DP1[i] = nums[i]
                DP2[i] = max(nums[0], nums[1])
            else:
                DP2[i] = max(DP2[i - 2] + nums[i], DP2[i - 1])
                if i == 2:
                    DP1[i] = max(nums[1], nums[2])
                else:
                    DP1[i] = max(DP1[i - 2] + nums[i], DP1[i - 1])
        print(DP1)
        print(DP2)
        if len(nums) == 1:
            return nums[0]
        else:
            return max(DP1[-1], DP2[-2])


data = Solution()
# nums = [1, 2, 3, 1]
# print(data.rob(nums))
# nums = [2, 3, 2]
# print(data.rob(nums))
# nums = [1, 2, 3]
# print(data.rob(nums))
nums = [200, 3, 140, 20, 10]
print(data.rob(nums))
# nums = [6,3,10,8,2,10,3,5,10,5,3]
# print(data.rob(nums))